import java.util.ArrayList;
import java.util.List;

public class Main {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    // 深搜

    // 257、二叉树的所有路径
    List<String> ret; // 创建全局变量，用来存储返回结果
    public List<String> binaryTreePaths(TreeNode root) {
        ret = new ArrayList();
        // 我们需要使用 StringBuilder 来连接当前节点的数值，并且把连接后的值传给下一个节点
        // 递归函数不需要返回值，因为直接王ret中放值
        dfs(root,new StringBuilder());
        return ret;
    }

    public void dfs(TreeNode root,StringBuilder path) {
        StringBuilder str  = new StringBuilder(path); // 为了达到 恢复现场 用的
        // 把传入的值和 root的值进行连接
        str.append(Integer.toString(root.val));
        // 先进行左右是否为空
        // 这也是递归结束条件
        if (root.left == null && root.right == null) {
            ret.add(str.toString());
            return;
        }

        // 有一个不为空就继续往不为空的地方去
        // 先把 -> 这个字符连接上
        str.append("->");

        // 遍历左
        if(root.left != null) { // 这个条件就是剪枝
            dfs(root.left,str);
        }
        if(root.right != null) { // 这个条件就是剪枝
            dfs(root.right,str);
        }
    }


    // 230、二叉搜索树中第k小的元素
    // 使用全局变量可以减少每次处理递归的时候要注意的细节
    int count; // 用来计数的，赋值为k
    int ret1; // 这个是我们要返回的值
    public int kthSmallest(TreeNode root, int k) {
        // 还是利用二叉搜索树的 中序遍历 是有序的这个特性
        // 按照 左根右 遍历。之后再处理根节点的时候呢，我们每到一个节点 count 就--，直至count为0的时候，说明这个root节点就是我们要的值
        count = k;
        dfs(root);
        return ret1;
    }

    public void dfs(TreeNode root) {
        // 递归的结束是当 root 为null或者count为0的时候
        if (root == null || count == 0) {
            return;
        }

        // 处理左子树
        dfs(root.left);

        // 处理根节点
        // 每次到节点的时候 count就要--一次
        count--;
        if(count == 0) {
            ret1 = root.val;
            // 剪枝
            // 当count == 0，说明这个节点的位置就是我们要的值，那么之后就不需要进行判断了
            return;
        }

        dfs(root.right);
    }


    // 98、验证二叉搜索树
    //利用中序遍历的特性(利用剪枝进行优化)
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        // 我们根据 二叉搜索树终须遍历的特点，来解决这个问题，中序遍历之后呢节点的排序是递增的
        // 所以我们可以根据这个特性来解决这个问题
        // 我们设置一个 全局变量 来比较每个节点的val值是否是大于这个全区变量的，这个全局变量呢是中序遍历中当前节点前一个节点的val值

        // 递归遍历的结束条件是root为null
        if (root == null) {
            // 根节点为空说明也是一个二叉搜索树
            return true;
        }

        // 左子树
        boolean left = isValidBST(root.left); // 返回的是左子树是否是二叉搜索树
        // 剪枝
        // 对于这个题就是当left 或者 根 或 right不是二叉搜索树的时候呢，就可以直接返回，也就是为false的时候
        if(left == false) {
            return false;
        }

        // 当这认为root的左子树已经判断结束了，现在判断根
        boolean cur = false;
        if(root.val > pre) {
            cur = true;
        }
        if(cur == false) {
            return false;
        }

        // 判断根节点之后更新pre，便于之后中序遍历进行比较
        pre = root.val;

        // 右子树
        boolean right = isValidBST(root.right);
        // 这里的right就不需要再判断了，因为下一行代码就是直接返回，无论是true或false都会返回

        // 返回判断 左根右 是否都是true
        return left && cur && right;
    }
    //递归方法
    long pre1 = Long.MIN_VALUE;
    public boolean isValidBST1(TreeNode root) {
        // 我们根据 二叉搜索树终须遍历的特点，来解决这个问题，中序遍历之后呢节点的排序是递增的
        // 所以我们可以根据这个特性来解决这个问题
        // 我们设置一个 全局变量 来比较每个节点的val值是否是大于这个全区变量的，这个全局变量呢是中序遍历中当前节点前一个节点的val值

        // 递归遍历的结束条件是root为null
        if (root == null) {
            // 根节点为空说明也是一个二叉搜索树
            return true;
        }

        // 左子树
        boolean left = isValidBST(root.left); // 返回的是左子树是否是二叉搜索树

        // 当这认为root的左子树已经判断结束了，现在判断根
        boolean cur = false;
        if(root.val > pre) {
            cur = true;
        }
        // 判断根节点之后更新pre，用于判断右子树
        pre1 = root.val;

        // 右子树
        boolean right = isValidBST(root.right);

        // 返回判断 左根右 是否都是true
        return left && cur && right;
    }


    // 814、二叉树剪枝
    public TreeNode pruneTree(TreeNode root) {
        // 我们的递归的 函数体 是需要返回我们根节点是什么的
        // 我们递归是先判断root节点的左子树是否为空，右子树是否为空，并且我们的root的值是否是0的时候，才可以进行判断是否需要删除这个子树
        // 删除子树也就是把其root节点值为空就可以了

        // 递归结束条件
        // 我们一直去递归左或者右节点直至为null才进行返回，因为我们的叶子节点也是一个子树
        if (root == null) {
            return null;
        }

        // 判断root的左子树和右子树的返回值，并且让对应的节点进行接收
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);

        // 这个时候就把左右判断完了，之后去判断是否需要删除这个root节点
        if (root.left == null && root.right == null && root.val == 0) {
            root = null;
        }

        return root;
    }



    // 129、求根节点到叶子节点数字之和
    public int sumNumbers(TreeNode root) {
        // 这个递归的子问题是需要做 4 步的
        // 1、我们要先给下一个root节点传入上一个节点计算的值，之后计算传入的值在当前root节点的值，
        // 比如4->9，那么传到9这个root的值是4，之后计算root位置的值是多少 4 * 10 + 9 ->49，就是当再往下一个节点传入的时候是49
        // 2、再计算root的左节点的数据，并返回
        // 3、再计算root的右节点的数据，并返回
        // 4、我们要把左右数据相加到一起返回
        // 这里要注意，在我们判断是否是递归结束的时候之前，先把步骤1做完，
        // 因为如果先做判断后计算。那么我们的叶子结点的值就没有和父结点整合

        return dfs(root,0); // 在一开始的时候传入的是0
    }

    public int dfs(TreeNode root,int preSum) {
        // 步骤1：
        preSum = preSum * 10 + root.val;
        // 判断递归结束条件
        if(root.left == null && root.right == null) {
            return preSum;
        }

        int ret = 0;
        // 步骤2：
        // 因为不是完全二叉树，所以可能存在 左为空又右为空 或 右为空左不为空 的情况
        if(root.left != null) {
            ret += dfs(root.left,preSum);
        }
        // 步骤3：
        if(root.right != null) {
            ret += dfs(root.right,preSum);
        }

        // 步骤4：
        return ret;
    }


    // 2331、计算布尔⼆叉树的值
    public boolean evaluateTree(TreeNode root) {
        // 二叉树使用递归，这个解决的子问题和主问题都是一样的，都是传入root求返回的是true还是false

        // 解决递归的结束条件
        // 当碰到叶子节点就结束递归
        if(root.left == null && root.right == null) {
            return root.val == 0 ? false : true;
        }

        // 递归root的左和右节点，相信函数一定会返回root左面的值和右面的值
        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);

        // 根据左右返回值和 root返回值
        return root.val == 2 ? left | right : left & right;
    }
}
